package problems;

import java.util.Iterator;
import java.util.List;

import lib.MathLib;
import lib.Permutations;

/**
 * The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes
 * and concatenating them in any order the result will always be prime. For
 * example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these
 * four primes, 792, represents the lowest sum for a set of four primes with
 * this property.
 * 
 * Find the lowest sum for a set of five primes for which any two primes
 * concatenate to produce another prime.
 * 
 * @author laszlo
 */
public class Euler060 extends AbstractEuler {

	@Override
	public Number calculate() {
		for (int i = 5; i < 10000; i++) {
			long primeIMaybeOverflow = MathLib.getPrime(i);
			if (primeIMaybeOverflow > Integer.MAX_VALUE) throw new NumberFormatException();
			int primeI = (int) primeIMaybeOverflow;
			for (int j = 4; j < i; j++) {
				int primeJ = (int)MathLib.getPrime(j);
				if (!allPermutationsArePrime(primeI, primeJ)) continue;
				for (int k = 3; k < j; k++) {
					int primeK = (int)MathLib.getPrime(k);
					if (!allPermutationsArePrime(primeI, primeJ, primeK)) continue;
					for (int l = 2; l < k; l++) {
						int primeL = (int)MathLib.getPrime(l);
						if (!allPermutationsArePrime(primeI, primeJ, primeK, primeL)) continue;
						for (int m = 2; m < l; m++) {
							int primeM = (int)MathLib.getPrime(m);
							if (allPermutationsArePrime(primeI,primeJ,primeK,primeL,primeM)) {
								return MathLib.getSum(primeI, primeJ, primeK, primeL, primeM);
							}
						}
					}
				}
			}
		}
		fail("no combinations found below 10000, check algorithm or increase upper bound");
		return null;
	}
	
	private boolean allPermutationsArePrime(Integer... numbers) {
		Iterator<List<Integer>> permutations = new Permutations<Integer>(2, numbers);
		while (permutations.hasNext()) {
			List<Integer> perm = permutations.next();
			StringBuffer strbuf = new StringBuffer();
			for (int digit : perm) {
				strbuf.append(digit);
			}
			if (!MathLib.isPrime(Integer.valueOf(strbuf.toString()))) return false;
		}
		return true;
	}

	@Override
	protected Number getCorrectAnswer() {
		return 26033L;
	}

}
